package Divide_and_conquer;

import java.util.ArrayList;
import java.util.List;



class point {
	double x;
	double y;
	point(double x,double y){
		this.x=x;
		this.y=y;
	}
}
public class divide {

	public static double dist(point p1,point p2) {
		return Math.sqrt(Math.pow((p2.x-p1.x), 2)+Math.pow((p2.y-p1.y), 2));
	}
	
	//按照坐标x进行的升序排序
	public static List<point> Sort_x(List<point> in){
		for(int i=0;i<in.size();i++) {
			for(int j=i;j<in.size();j++) {
				if(in.get(i).x>in.get(j).x) {
					double temp_x=in.get(i).x;
					double temp_y=in.get(i).y;
					in.set(i, in.get(j));
					in.set(j, new point(temp_x,temp_y));
				}
			}
		}
		return in;
	}
	
	//按照坐标y进行的升序排序
		public static List<point> Sort_y(List<point> in){
			for(int i=0;i<in.size();i++) {
				for(int j=i;j<in.size();j++) {
					if(in.get(i).y>in.get(j).y) {
						double temp_x=in.get(i).x;
						double temp_y=in.get(i).y;
						in.set(i, in.get(j));
						in.set(j, new point(temp_x,temp_y));
					}
				}
			}
			return in;
		}
	//本函数输入in:全部点集，low:in中需要用到的下标下限，high:in中需要用到的下标上限，rec:用于记录最终的最近对两点，输出：最近对的距离
	static double Nearest_point_pair(List<point> in,int low,int high,List<point> rec) {
		 double d1,d2,d3,d;
		 int mid,i,j,index;
		 //point[] P=new point[high-low+1];
		 List<point> P=new ArrayList<point>(high-low+1);
		 point[] temp1=new point[2];
		 point[] temp2=new point[2];
		 if(high==low) {
			 return 0;
		 }
		 if(high-low==1) {
			 rec.clear();
			 rec.add(in.get(low));
			 rec.add(in.get(high));
			 return dist(in.get(low),in.get(high));
		 }
		 if(high-low==2){
			 d1=dist(in.get(low),in.get(low+1));
			 d2=dist(in.get(low+1),in.get(high));
			 d3=dist(in.get(low),in.get(high));
			 if((d1<d2)&&(d1<d3)){
				 	rec.clear();
		            rec.add(in.get(low));
		            rec.add(in.get(low+1));
		            return d1;
		        }
		        else if(d2<d3){
		        	rec.clear();
		            rec.add(in.get(low+1));
		            rec.add(in.get(high));
		            return d2;
		        }
		        else {
		        	rec.clear();
		            rec.add(in.get(low));
		            rec.add(in.get(high));
		            return d3;
		        }
		 }
		 mid=(low+high)/2;
		 d1=Nearest_point_pair(in,low,mid,rec);
		 temp1[0]=rec.get(0);
		 temp1[1]=rec.get(1);
		 d2=Nearest_point_pair(in,mid+1,high,rec);
		 temp2[0]=rec.get(0);
		 temp2[1]=rec.get(1);
		 if(d1<d2) {
			 d=d1;
			 rec.clear();
			 rec.add(temp1[0]);
			 rec.add(temp1[1]);
		 }else {
			 d=d2;
			 rec.clear();
			 rec.add(temp2[0]);
			 rec.add(temp2[1]);
		 }
		 index=0;
		 for(i=mid;(i>=low)&&((in.get(mid).x-in.get(i).x)<d);i--){//找出位于中间点左侧且x坐标范围在d之间的点
			 index++;
			 P.add(in.get(i));
		 }
		 for(i=mid+1;(i<=high)&&((in.get(i).x-in.get(mid).x)<d);i++) {//找出位于中间点右侧且x坐标范围在d之间的点
			 index++;
			 P.add(in.get(i));
		 }
		 P=Sort_y(P);
		 for(i=0;i<index;i++) {
			 for(j=i+1;j<index;j++) {//??
				 if((P.get(j).y-P.get(i).y)>=d)
					 break;
				 else {
					 d3=dist(P.get(i),P.get(j));
					 if(d3<d) {
						 rec.clear();
						 rec.add(P.get(i));
						 rec.add(P.get(j));
						 d=d3;
					 }
				 }
			 }
		 }
		 return d;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		point a1=new point(569,738);
		point a2=new point(231,433);
		point a3=new point(345,987);
		point a4=new point(564,897);
		point a5=new point(134,897);
		point a6=new point(908,234);
		point a7=new point(687,343);
		point a8=new point(569,246);
		point a9=new point(679,146);
		point a0=new point(681,874);
		List<point> in=new ArrayList<point>();
		in.add(a1);in.add(a0);in.add(a9);in.add(a8);in.add(a7);in.add(a6);in.add(a5);in.add(a4);in.add(a3);in.add(a2);
		List<point> rec=new ArrayList<point>(122);
		double d=Nearest_point_pair(in,0,in.size()-1,rec);
		System.out.println(d);
		System.out.println(rec.size());
	}

}
